//
// Created by Shao Wenhan on 2021/9/28.
//

#ifndef FINDANDUPDATEMEDIAN_MEDIANOFUNABATEDARRAY_H
#define FINDANDUPDATEMEDIAN_MEDIANOFUNABATEDARRAY_H

#include <vector>
#include <queue>
#include "Log.h"
using namespace std;

template<typename T>
class MedianOfUnabatedArray {
private:
    // the size of m_maxHeap is equal to or one smaller than the size of m_minHeap.
    // the first half of numbers are put in the m_maxHeap and the second half of ones are in the m_minHeap.
    priority_queue<T> m_maxHeap;
    priority_queue<T, vector<T>, greater<T>> m_minHeap;
public:
    void initial();
    void insert(T num);
    double getMedian() const;
};

template<typename T>
void MedianOfUnabatedArray<T>::initial() {
    priority_queue<T> emptyMaxHeap;
    priority_queue<T, vector<T>, greater<T>> emptyMinHeap;
    swap(m_maxHeap, emptyMaxHeap);
    swap(m_minHeap, emptyMinHeap);
}

template<typename T>
void MedianOfUnabatedArray<T>::insert(T num) {
    if(m_minHeap.empty() or m_minHeap.top() <= num)
        m_minHeap.push(num);
    else
        m_maxHeap.push(num);

    if(m_maxHeap.size() > m_minHeap.size()){
        m_minHeap.push(m_maxHeap.top());
        m_maxHeap.pop();
    }
    else if(m_maxHeap.size()+1 < m_minHeap.size()){
        m_maxHeap.push(m_minHeap.top());
        m_minHeap.pop();
    }
}

template<typename T>
double MedianOfUnabatedArray<T>::getMedian() const {
    if(m_maxHeap.size() == m_minHeap.size())
        return static_cast<double>((m_maxHeap.top()+m_minHeap.top())*0.5);
    else
        return static_cast<double>(m_minHeap.top());
}

#endif //FINDANDUPDATEMEDIAN_MEDIANOFUNABATEDARRAY_H
